/*
 * Copyright (c) 2009-2010 HIT Microelectronic Center
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Gou Pengfei
 *
 * Date:    Jan. 2011
 *
 * */

#include "base/intmath.hh"
#include "cpu/edge/pred/piecewise.hh"
#include "cpu/base.hh"

template<class Impl>
PiecewiseBP<Impl>::PiecewiseBP(DerivEdgeCPUParams *params)
    : BaseBinaryPredictor<Impl>(params, "Piecewise"),
    historyBits(params->pwHistoryBits + 1),
    localHistoryBits(params->pwLocalHistoryBits),
    pathTableSize(params->pwPathTableSize),
    tableSize(params->pwTableSize),
    localHistoryTableSize(params->pwLocalHistoryTableSize),
    weightBits(params->weightBits),
    blockShiftAmt(params->blockShiftAmt)
{
    initVars();
} 

template<class Impl>
PiecewiseBP<Impl>::PiecewiseBP(int history_bits, int local_history_bits,
        int path_table_size, int table_size, int local_history_table_size,
        unsigned weight_bits, unsigned block_shift_amt)
    : historyBits(history_bits + 1),
    localHistoryBits(local_history_bits),
    pathTableSize(path_table_size),
    tableSize(table_size),
    localHistoryTableSize(local_history_table_size),
    weightBits(weight_bits),
    blockShiftAmt(block_shift_amt)
{
    initVars();
}

template<class Impl>
void
PiecewiseBP<Impl>::initVars()
{
    // Initialized to SingleBitHistory. 
    mode = SingleBitHistory;

    // Initialize three masks, which will be used to index the weight
    // table.
    historyMask = (ULL(0x1) << historyBits) - 1;

    // If we get a pathTableSize with 0 (or a negative value), that
    // means we just have one entry (the bias entry) for the second
    // demension.
    if (pathTableSize > 0) {
        pathAddrMask = (ULL(0x1) << floorLog2(pathTableSize)) - 1;
    } else {
        pathAddrMask = ULL(0x0);
        pathTableSize = 0;
    }

    indexPCMask = (ULL(0x1) << floorLog2(tableSize)) - 1;

    // Initialize the local history mask.
    localHistoryMask = (ULL(0x1) << localHistoryBits) - 1;

    localHistoryTableMask = (ULL(0x1) << floorLog2(localHistoryTableSize)) - 1;

    exitIdBits = floorLog2(TheISA::MaxExitsInBlock);

    typeIdBits = floorLog2(TheISA::NumBranchType);

    DPRINTF(PiecewiseBP, "Init piecewise BP. History length:%i;"
            " path table size:%i; table size:%i;\n"
            "History mask:%#x; path addr mask:%#x; index pc mask:%#x\n"
            "Exit bits: %i\n"
            "Type bits: %i\n",
            historyBits, pathTableSize, tableSize,
            historyMask, pathAddrMask, indexPCMask,
            exitIdBits, typeIdBits);

    // The threshold is given by Jimenez's Micro'03 paper
    threshold = 2.14 * (historyBits + 1) + 20.58;

    //          weightTable Structure
    //
    //   |---------Size = historyBits---------| -
    // -------------------------------------  | 
    // |  |  |  |  |  | ... |  |  |  |  |  |  | 
    // -------------------------------------  | 
    // |  |  |  |  |  | ... |  |  |  |  |  |  | 
    // -------------------------------------  | Size = pathTableSize
    // |  |  |  |  |  | ... |  |  |  |  |  |  | 
    // -------------------------------------  | 
    // |  |  |  |  |  | ... |  |  |  |  |  |  | 
    // -------------------------------------  | 
    // |  |  |  |  |  | ... |  |  |  |  |  |--| -
    // -------------------------------------   / 
    // |  |  |  |  |  | ... |  |  |  |  |  |  / Size = tableSize
    // ------------------------------------- -
    //
    weightTable.resize(tableSize, NULL);

    for (int i = 0 ; i < tableSize; ++i) {
        // Create a path table entry
        TwoDimWeightTable * path_table = new TwoDimWeightTable;
        // We need an extra entry for the bias weight.
        (*path_table).resize(pathTableSize + 1, NULL);
        weightTable[i] = path_table;

        for (int j = 0; j < pathTableSize + 1; j++) {
            // Create a table entry
            WeightTableEntry * weight_entry = new WeightTableEntry;
            (*weight_entry).resize(historyBits, static_cast<int>(0));
            (*(weightTable[i]))[j] = weight_entry;
        }
    }
    
    for (int i = 0; i < Impl::MaxThreads; ++i) {
        historyTable[i] = 0;
        pathHistoryTable[i].resize(historyBits, static_cast<Addr>(0));
        currentLocalHistory[i] = 0;
    }

    for (int i = 0; i < Impl::MaxInFlightBlockNum; ++i) {
        historyFile[i] = 0;
        pathHistoryFile[i].resize(historyBits, static_cast<Addr>(0));
    }

    // Local history staff initialization. 
    
    // Initialize the local weight table separately from the three-dim
    // global weight table.
    localWeightTable.resize(tableSize, NULL);

    for (int i = 0; i < tableSize; i++) {
        WeightTableEntry * weight_entry = new WeightTableEntry;
        (*weight_entry).resize(localHistoryBits, static_cast<int>(0));
        localWeightTable[i] = weight_entry;
    }

    // Initialize the local history table.
    localHistoryTable.resize(localHistoryTableSize, static_cast<uint64_t>(0));

    // Initialize the local future file.
    for (int i = 0; i < Impl::MaxInFlightBlockNum; i++) {
        localFutureFile[i].index = 0;
        localFutureFile[i].history = 0;
    }

    maxWeight = (1 << (weightBits - 1)) - 1;

    minWeight = -(1 << (weightBits - 1));
}

template<class Impl>
PiecewiseBP<Impl>::~PiecewiseBP()
{
    // Deleting the table
    for (int i = 0 ; i < tableSize; ++i) {
        if (weightTable[i]) {
            for (int j = 0; j < pathTableSize + 1; j++) {
                if ((*(weightTable[i]))[j]) {
                    delete (*(weightTable[i]))[j];
                }
            }
            delete weightTable[i];
        }
    }

    for (int i = 0; i < tableSize; ++i) {
        if (localWeightTable[i]) {
            delete localWeightTable[i];
        }
    }
}

template<class Impl>
void
PiecewiseBP<Impl>::initMode(PiecewiseMode init_mode)
{
    assert(init_mode == SingleBitHistory ||
           init_mode == ExitHistory ||
           init_mode == TypeHistory);

    mode = init_mode;
}

template<class Impl>
void
PiecewiseBP<Impl>::reset()
{
    assert(weightTable.size() == tableSize);
    assert(localWeightTable.size() == tableSize);

    for (int i = 0 ; i < tableSize; ++i) {
        assert(weightTable[i]);
        assert((*weightTable[i]).size() == pathTableSize + 1);

        for (int j = 0; j < pathTableSize + 1; j++) {
            assert((*(weightTable[i]))[j]);
            assert((*((*(weightTable[i]))[j])).size() == historyBits);

            for (int k = 0; k < historyBits; k++) {
                (*((*(weightTable[i]))[j]))[k] = 0;
            }
        }

        for (int j = 0; j < localHistoryBits; j++) {
            (*(localWeightTable[i]))[j] = 0;
        }
    }

    for (int i = 0; i < Impl::MaxThreads; ++i) {
        historyTable[i] = 0;
        currentLocalHistory[i] = 0;

        assert(pathHistoryTable[i].size() == historyBits);

        for (int j = 0; j < historyBits; j++) {
            pathHistoryTable[i][j] = 0;
        }
    }

    for (int i = 0; i < Impl::MaxInFlightBlockNum; ++i) {
        historyFile[i] = 0;

        assert(pathHistoryFile[i].size() == historyBits);

        for (int j = 0; j < historyBits; j++) {
            pathHistoryFile[i][j] = 0;
        }

        sumTable[i] = 0.0;

        localFutureFile[i].index = 0;
        localFutureFile[i].history = 0;
    }

    for (int i = 0; i < localHistoryTableSize; i++) {
        localHistoryTable[i] = 0;
    }
}

template<class Impl>
bool
PiecewiseBP<Impl>::lookup(BlockID block_id, BlockID oldest_block_id,
        Addr block_pc, ThreadID tid)
{
    bool prediction;

    assert(mode != Unknown);

    currentLocalHistory[tid] = getSpeculativeLocalHistory(block_id,
                                                          oldest_block_id,
                                                          block_pc,
                                                          tid);

    // Global history will be speculatively updated later and local
    // history will be speculatively updated during lookup 
    prediction = predictorLookup(block_id, block_pc, tid);

    if (mode == SingleBitHistory) {
        speculativeUpdate(block_pc, block_id, prediction, tid);
    }
    
    return prediction;
}

template<class Impl>
bool
PiecewiseBP<Impl>::update(BlockID block_id, Addr block_pc, ThreadID tid,
        bool prediction, bool mispredicted)
{
    // Only need to update weight table, because history and path
    // should have been updated speculatively before or been updated
    // in squash handling procedure when misprediction occurs.
    double pre_sum_abs = fabs(sumTable[block_id & (Impl::MaxInFlightBlockNum - 1)]);

    if (pre_sum_abs < threshold || mispredicted) {
        updateWeightTable(block_id, block_pc, prediction, tid);
    }

    if (mode == SingleBitHistory) {
        updateLocalHistoryTable(block_id, block_pc, prediction, tid);
    }

    // This return is meaningless. It is just for interface coherence.
    return false;
}

template<class Impl>
void
PiecewiseBP<Impl>::squash(BlockID block_id, ThreadID tid)
{
    int speculative_frame = block_id & (Impl::MaxInFlightBlockNum - 1);

    // Restore the history
    historyTable[tid] = historyFile[speculative_frame];

    // Restore the path
    pathHistoryTable[tid] = pathHistoryFile[speculative_frame];

    // Clear the local future file
    for (int i = 0; i < Impl::MaxInFlightBlockNum; i++) {
        localFutureFile[i].index = 0;
        localFutureFile[i].history = 0;
    }

    DPRINTF(PiecewiseBP,"[Bid:%lli][SF:%i],squashed.\n",
            block_id,
            speculative_frame);
}

template<class Impl>
void
PiecewiseBP<Impl>::squash(Addr block_pc, BlockID block_id,
        bool prediction, ThreadID tid)
{
    int speculative_frame = block_id & (Impl::MaxInFlightBlockNum - 1);

    // Squash global history and global path history
    uint64_t history = historyFile[speculative_frame];

    assert(mode == SingleBitHistory);

    historyTable[tid] = updateHistory(history, prediction, true);

    PathHistory path = pathHistoryFile[speculative_frame];

    updatePathHistory(path, block_pc);

    pathHistoryTable[tid] = path;

    // Squash local history
    LFFEntry old_entry = localFutureFile[speculative_frame];

    for (int i = 0; i < Impl::MaxInFlightBlockNum; i++) {
        localFutureFile[i].index = 0;
        localFutureFile[i].history = 0;
    }

    uint64_t local_history = updateHistory(old_entry.history, prediction,
                                           false);
    LFFEntry new_entry;
    new_entry.history = local_history;
    new_entry.index = old_entry.index;

    localFutureFile[speculative_frame] = new_entry;

    DPRINTF(PiecewiseBP,"[Bid:%lli][SF:%i], squashed due to branch"
            "mispredicted(real pred:%i).\n",
            block_id,
            speculative_frame,
            prediction);
}

template<class Impl>
void
PiecewiseBP<Impl>::squash(Addr block_pc, BlockID block_id,
        TheISA::ExitID exit_id, ThreadID tid)
{
    int speculative_frame = block_id & (Impl::MaxInFlightBlockNum - 1);

    uint64_t history = historyFile[speculative_frame];

    assert(mode == ExitHistory);
    assert(exit_id >= 0 && exit_id < TheISA::MaxExitsInBlock);

    historyTable[tid] = updateHistory(history, exit_id, true);

    PathHistory path = pathHistoryFile[speculative_frame];

    updatePathHistory(path, block_pc, exit_id);

    pathHistoryTable[tid] = path;

    // Squash local history
    LFFEntry old_entry = localFutureFile[speculative_frame];

    for (int i = 0; i < Impl::MaxInFlightBlockNum; i++) {
        localFutureFile[i].index = 0;
        localFutureFile[i].history = 0;
    }

    uint64_t local_history = updateHistory(old_entry.history, exit_id,
                                           false);
    LFFEntry new_entry;
    new_entry.history = local_history;
    new_entry.index = old_entry.index;

    localFutureFile[speculative_frame] = new_entry;

    DPRINTF(PiecewiseBP,"[Bid:%lli][SF:%i], squashed due to branch"
            "mispredicted(real EXIT_ID[%i]).\n",
            block_id,
            speculative_frame,
            exit_id);
}

template<class Impl>
void
PiecewiseBP<Impl>::squash(Addr block_pc, BlockID block_id,
        TheISA::BTypeID type_id, ThreadID tid)
{
    int speculative_frame = block_id & (Impl::MaxInFlightBlockNum - 1);

    uint64_t history = historyFile[speculative_frame];

    assert(mode == TypeHistory);
    assert(type_id >= 0 && type_id < TheISA::NumBranchType);

    historyTable[tid] = updateHistory(history, type_id, true);

    PathHistory path = pathHistoryFile[speculative_frame];

    updatePathHistory(path, block_pc, type_id);

    pathHistoryTable[tid] = path;

    // Squash local history
    LFFEntry old_entry = localFutureFile[speculative_frame];

    for (int i = 0; i < Impl::MaxInFlightBlockNum; i++) {
        localFutureFile[i].index = 0;
        localFutureFile[i].history = 0;
    }

    uint64_t local_history = updateHistory(old_entry.history, type_id,
                                           false);
    LFFEntry new_entry;
    new_entry.history = local_history;
    new_entry.index = old_entry.index;

    localFutureFile[speculative_frame] = new_entry;

    DPRINTF(PiecewiseBP,"[Bid:%lli][SF:%i], squashed due to branch"
            "mispredicted(real EXIT_ID[%i]).\n",
            block_id,
            speculative_frame,
            type_id);
}

template<class Impl>
bool
PiecewiseBP<Impl>::predictorLookup(BlockID block_id, Addr block_pc, ThreadID tid)
{
    double sum;

    uint64_t history = historyTable[tid];

    int table_idx = (block_pc >> blockShiftAmt) & indexPCMask;

    DPRINTF(BPDEBUG, "Lookuping table, history:%#x\n", history);

    assert(mode != Unknown);

    // Lookup the bias weight
    sum = lookupTable(table_idx, 0, 0, true) / 0.1111;

    // Lookup the global weight table
    for (int i = 1; i < historyBits; ++i) {

        Addr path_addr = pathHistoryTable[tid][i - 1];

        int path_idx = -1;

        if (pathTableSize != 0) { 
            path_idx = path_addr & pathAddrMask;
        }         

        if ((history >> (i - 1)) & 0x1) {
            sum += lookupTable(table_idx, path_idx + 1, i, true)  
                   / (0.1111 + 0.037 * ((double)(i)));
        } else {
            sum -= lookupTable(table_idx, path_idx + 1, i, true) 
                   / (0.1111 + 0.037 * ((double)(i)));
        }       
    }

    uint64_t local_history = currentLocalHistory[tid];

    for (int i = 0; i < localHistoryBits; ++i) {

        if ((local_history >> i) & 0x1) {
            sum += lookupTable(table_idx, 0, i, false)  
                   / (0.1111 + 0.037 * ((double)(i + 1)));
        } else {
            sum -= lookupTable(table_idx, 0, i, false) 
                   / (0.1111 + 0.037 * ((double)(i + 1)));
        }       
    }
   
    DPRINTF(BPDEBUG,"sum = %.6lf.\n",sum);

    sumTable[block_id & (Impl::MaxInFlightBlockNum - 1)] = sum;

    if (sum >= 0) {
        return true;
    }

    return false;
}

template<class Impl>
void
PiecewiseBP<Impl>::updateWeightTable(BlockID block_id, 
        Addr block_pc, bool prediction, ThreadID tid)
{
    int speculative_frame = block_id & (Impl::MaxInFlightBlockNum - 1);

    uint64_t history = historyFile[speculative_frame];

    int table_idx = (block_pc >> blockShiftAmt) & indexPCMask;

    DPRINTF(BPDEBUG, "Updating table, history:%#x, prediction:%i\n",
            history, prediction);

    // Update the bias weight
    if (prediction) {
        if (lookupTable(table_idx, 0, 0, true) < maxWeight) {
            incWeight(table_idx, 0, 0, true);
        }
    } else {
        if (lookupTable(table_idx, 0, 0, true) > minWeight) {
            decWeight(table_idx, 0, 0, true);
        }
    }

    // Update the global weight table
    for (unsigned i = 1 ; i < historyBits; ++i) {

        Addr path_addr = pathHistoryFile[speculative_frame][i - 1];

        int path_idx = -1;

        if (pathTableSize != 0) { 
            path_idx = path_addr & pathAddrMask;
        }         

        if (((history >> (i - 1)) & 0x1) == prediction) {
            if (lookupTable(table_idx, path_idx + 1, i, true) < maxWeight) {
                incWeight(table_idx, path_idx + 1, i, true);
            }    
        } else {
            if (lookupTable(table_idx, path_idx + 1, i, true) > minWeight) {
                decWeight(table_idx, path_idx + 1, i, true);
            }
        }
    }

    // Update the local weight table
    uint64_t local_history = localFutureFile[speculative_frame].history;

    for (unsigned i = 0 ; i < localHistoryBits; ++i) {

        if (((local_history >> i) & 0x1) == prediction) {
            if (lookupTable(table_idx, 0, i, false) < maxWeight) {
                incWeight(table_idx, 0, i, false);
            }    
        } else {
            if (lookupTable(table_idx, 0, i, false) > minWeight) {
                decWeight(table_idx, 0, i, false);
            }
        }
    }
    
    DPRINTF(PiecewiseBP,"[Bid:%i,PC:%#x]: updated(%i).\n",
            block_id, block_pc, prediction);
}

template<class Impl>
uint64_t
PiecewiseBP<Impl>::getSpeculativeLocalHistory(BlockID block_id,
        BlockID oldest_block_id, Addr block_pc, ThreadID tid)
{
    // Lookup the local weight table
    int local_history_idx = (block_pc >> blockShiftAmt) &
                            localHistoryTableMask;

    uint64_t local_history = localHistoryTable[local_history_idx];

    if (block_id != oldest_block_id && oldest_block_id != 0) {

        BlockID tmp_spec_frame_id = block_id; // youngest block frame id
        BlockID oldest_spec_frame_id = oldest_block_id &
                                       (Impl::MaxInFlightBlockNum - 1);
        do {
            LFFEntry lff_entry;
            tmp_spec_frame_id = (tmp_spec_frame_id - 1) &
                                (Impl::MaxInFlightBlockNum - 1);
            lff_entry = localFutureFile[tmp_spec_frame_id];
            if (lff_entry.index == local_history_idx)
            {
                local_history = lff_entry.history;
                break;
            }
        } while (tmp_spec_frame_id != oldest_spec_frame_id);
    }

    return local_history;
}

template<class Impl>
void
PiecewiseBP<Impl>::updateLocalHistoryTable(BlockID block_id, 
        Addr block_pc, bool prediction, ThreadID tid)
{
    assert(mode == SingleBitHistory);

    int local_history_idx = (block_pc >> blockShiftAmt) &
                            localHistoryTableMask;

    uint64_t old_history = localHistoryTable[local_history_idx];

    localHistoryTable[local_history_idx] =
        updateHistory(old_history, prediction, false);
}

template<class Impl>
void
PiecewiseBP<Impl>::updateLocalHistoryTable(BlockID block_id, 
        Addr block_pc, TheISA::ExitID exit_id, ThreadID tid)
{
    assert(mode == ExitHistory);
    assert(exit_id >= 0 && exit_id < TheISA::MaxExitsInBlock);

    int local_history_idx = (block_pc >> blockShiftAmt) &
                            localHistoryTableMask;

    uint64_t old_history = localHistoryTable[local_history_idx];

    localHistoryTable[local_history_idx] =
        updateHistory(old_history, exit_id, false);
}

template<class Impl>
void
PiecewiseBP<Impl>::updateLocalHistoryTable(BlockID block_id, 
        Addr block_pc, TheISA::BTypeID type_id, ThreadID tid)
{
    assert(mode == TypeHistory);
    assert(type_id >= 0 && type_id < TheISA::NumBranchType);

    int local_history_idx = (block_pc >> blockShiftAmt) &
                            localHistoryTableMask;

    uint64_t old_history = localHistoryTable[local_history_idx];

    localHistoryTable[local_history_idx] =
        updateHistory(old_history, type_id, false);
}

template<class Impl>
uint64_t 
PiecewiseBP<Impl>::updateHistory(uint64_t history, bool prediction,
        bool is_global)
{
    uint64_t new_history;

    assert(mode == SingleBitHistory);

    new_history = prediction ? ((history << 1) | ULL(0x1)) : (history << 1);

    if (is_global) {
        new_history &= historyMask;
    } else {
        new_history &= localHistoryMask;
    }

    DPRINTF(PiecewiseBP, "Update history for prediction[%i]."
            " Before: %#x; After: %#x\n",
            prediction,
            history, new_history);

    return new_history;
}

template<class Impl>
uint64_t
PiecewiseBP<Impl>::updateHistory(uint64_t history, TheISA::ExitID exit_id,
        bool is_global)
{
    assert(mode == ExitHistory);
    assert(exit_id >= 0 && exit_id < TheISA::MaxExitsInBlock);

    uint64_t new_history;

    new_history = (history << (exit_id + 1)) | ULL(0x1);

    if (is_global) {
        new_history &= historyMask;
    } else {
        new_history &= localHistoryMask;
    }

    DPRINTF(PiecewiseBP, "Update history for EXIT_ID[%i]."
            " Before: %#x; After: %#x\n",
            exit_id,
            history, new_history);

    return new_history;
}

template<class Impl>
uint64_t
PiecewiseBP<Impl>::updateHistory(uint64_t history, TheISA::BTypeID type_id,
        bool is_global)
{
    assert(mode == TypeHistory);
    assert(type_id >= 0 && type_id < TheISA::NumBranchType);

    uint64_t new_history;

    new_history = (history << typeIdBits) | (uint64_t)type_id;

    if (is_global) {
        new_history &= historyMask;
    } else {
        new_history &= localHistoryMask;
    }

    DPRINTF(PiecewiseBP, "Update history for TYPE_ID[%i]."
            " Before: %#x; After: %#x\n",
            type_id,
            history, new_history);

    return new_history;
}

template<class Impl>
void 
PiecewiseBP<Impl>::updatePathHistory(PathHistory &path_history, Addr new_pc)
{
    assert(mode == SingleBitHistory);

    DPRINTF(PiecewiseBP, "Update path history,"
            " Pop: %#x; Push: %#x\n",
            path_history.back(),
            new_pc);

    path_history.pop_back();

    new_pc >>= blockShiftAmt;

    path_history.push_front(new_pc);
}

template<class Impl>
void
PiecewiseBP<Impl>::updatePathHistory(PathHistory &path_history, Addr new_pc,
        TheISA::ExitID exit_id)
{
    assert(mode == ExitHistory);
    assert(exit_id >= 0 && exit_id < TheISA::MaxExitsInBlock);

    // Each exit id will produce multiple paths because exit id will
    // result in multiple bits in history.
    for (int i = 0; i < exit_id + 1; i++) {

        DPRINTF(PiecewiseBP, "Update path history for EXIT_ID[%i],"
                " Pop: %#x; Push: %#x\n",
                exit_id,
                path_history.back(),
                new_pc);

        path_history.pop_back();

        new_pc >>= blockShiftAmt;
        new_pc <<= exitIdBits;
        new_pc |= (Addr)i;

        path_history.push_front(new_pc);
    }
}

template<class Impl>
void
PiecewiseBP<Impl>::updatePathHistory(PathHistory &path_history, Addr new_pc,
        TheISA::BTypeID type_id)
{
    assert(mode == TypeHistory);
    assert(type_id >= 0 && type_id < TheISA::NumBranchType);

    // Each exit id will produce multiple paths because type id will
    // result in multiple bits in history.
    for (int i = 0; i < typeIdBits; i++) {

        DPRINTF(PiecewiseBP, "Update path history for TYPE_ID[%i],"
                " Pop: %#x; Push: %#x\n",
                type_id,
                path_history.back(),
                new_pc);

        path_history.pop_back();

        new_pc >>= blockShiftAmt;
        new_pc <<= typeIdBits;
        new_pc |= (Addr)type_id;

        path_history.push_front(new_pc);
    }
}

template<class Impl>
void
PiecewiseBP<Impl>::speculativeUpdate(Addr new_pc, BlockID block_id,
        bool prediction, ThreadID tid)
{
    assert(mode == SingleBitHistory);

    int speculative_frame = block_id & (Impl::MaxInFlightBlockNum - 1);

    DPRINTF(PiecewiseBP, "[Tid:%i]:Speculatively update history and path"
            " for block[Bid:%lli] in speculative frame[SF:%i]\n",
            tid,
            block_id,
            speculative_frame);

    // Update history
    uint64_t history = historyTable[tid];

    historyFile[speculative_frame] = historyTable[tid];
    
    historyTable[tid] = updateHistory(history, prediction, true);

    // Update path
    PathHistory path = pathHistoryTable[tid];

    pathHistoryFile[speculative_frame] = pathHistoryTable[tid];

    updatePathHistory(path, new_pc);

    pathHistoryTable[tid] = path;

    // Update local history
    uint64_t local_history_old = currentLocalHistory[tid];
    uint64_t local_history_new = updateHistory(local_history_old, prediction,
            false);

    LFFEntry new_entry;
    new_entry.history = local_history_new;
    new_entry.index = (new_pc >> blockShiftAmt) & localHistoryTableMask;

    localFutureFile[speculative_frame] = new_entry;
}

template<class Impl>
void
PiecewiseBP<Impl>::speculativeUpdate(Addr new_pc, BlockID block_id,
        TheISA::ExitID exit_id, ThreadID tid)
{
    assert(mode == ExitHistory);
    assert(exit_id >= 0 && exit_id < TheISA::MaxExitsInBlock);

    int speculative_frame = block_id & (Impl::MaxInFlightBlockNum - 1);

    DPRINTF(PiecewiseBP, "[Tid:%i]:Speculatively update history and path"
            " for block[Bid:%lli] in speculative frame[SF:%i]\n",
            tid,
            block_id,
            speculative_frame);

    // Update history
    uint64_t history = historyTable[tid];

    historyFile[speculative_frame] = historyTable[tid];
    
    historyTable[tid] = updateHistory(history, exit_id, true);

    // Update path
    PathHistory path = pathHistoryTable[tid];

    pathHistoryFile[speculative_frame] = pathHistoryTable[tid];

    updatePathHistory(path, new_pc, exit_id);

    pathHistoryTable[tid] = path;

    // Update local history
    uint64_t local_history_old = currentLocalHistory[tid];
    uint64_t local_history_new = updateHistory(local_history_old, exit_id,
            false);

    LFFEntry new_entry;
    new_entry.history = local_history_new;
    new_entry.index = (new_pc >> blockShiftAmt) & localHistoryTableMask;

    localFutureFile[speculative_frame] = new_entry;
}

template<class Impl>
void
PiecewiseBP<Impl>::speculativeUpdate(Addr new_pc, BlockID block_id,
        TheISA::BTypeID type_id, ThreadID tid)
{
    assert(mode == TypeHistory);
    assert(type_id >= 0 && type_id < TheISA::NumBranchType);

    int speculative_frame = block_id & (Impl::MaxInFlightBlockNum - 1);

    DPRINTF(PiecewiseBP, "[Tid:%i]:Speculatively update history and path"
            " for block[Bid:%lli] in speculative frame[SF:%i]\n",
            tid,
            block_id,
            speculative_frame);

    // Update history
    uint64_t history = historyTable[tid];

    historyFile[speculative_frame] = historyTable[tid];
    
    historyTable[tid] = updateHistory(history, type_id, true);

    // Update path
    PathHistory path = pathHistoryTable[tid];

    pathHistoryFile[speculative_frame] = pathHistoryTable[tid];

    updatePathHistory(path, new_pc, type_id);

    pathHistoryTable[tid] = path;

    // Update local history
    uint64_t local_history_old = currentLocalHistory[tid];
    uint64_t local_history_new = updateHistory(local_history_old, type_id,
            false);

    LFFEntry new_entry;
    new_entry.history = local_history_new;
    new_entry.index = (new_pc >> blockShiftAmt) & localHistoryTableMask;

    localFutureFile[speculative_frame] = new_entry;
}

template<class Impl>
uint64_t
PiecewiseBP<Impl>::getGlobalHistory(BlockID block_id, ThreadID tid)
{
    int speculative_frame = block_id & (Impl::MaxInFlightBlockNum - 1);
    return historyFile[speculative_frame] & historyMask;
}

template<class Impl>
uint64_t
PiecewiseBP<Impl>::getPathHistory(BlockID block_id, ThreadID tid)
{
    int speculative_frame = block_id & (Impl::MaxInFlightBlockNum - 1);

    PathHistory path = pathHistoryFile[speculative_frame];
    uint64_t path_hist = 0;

    for (int i = 0; i < path.size(); i++) {
        if (i < 16) {
            // Take 4 bits from each path address
            path_hist |= ((path[i] & ULL(0xF)) << (i * 4));
        }
    }

    return path_hist;
}

